#!/usr/bin/env python
# -*- coding:utf-8 -*-
# @Author  : 邢建辉
# @Email   : xjh_0125@sina.com
# @Time    : 2021/8/17 9:59
# @Software: PyCharm
# @File    : l207_course_schedule.py


class Solution:
    def __init__(self):
        """
        你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。
        在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程  bi 。
        例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。
        请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。

        示例 1：
        输入：numCourses = 2, prerequisites = [[1,0]]
        输出：true
        解释：总共有 2 门课程。学习课程 1 之前，你需要完成课程 0 。这是可能的。
        示例 2：
        输入：numCourses = 2, prerequisites = [[1,0],[0,1]]
        输出：false
        解释：总共有 2 门课程。学习课程 1 之前，你需要先完成​课程 0 ；并且学习课程 0 之前，你还应先完成课程 1 。这是不可能的。
        """
        self.onPath = []
        self.visted = []
        self.hasCiycle = False

    def buildGraph(self, numCourses, prerequisites):
        graph = [[] for i in range(numCourses)]
        for arr in prerequisites:
            graph[arr[0]].append(arr[1])
        return graph

    def canFinish(self, numCourses, prerequisites):
        """
        :type numCourses: int
        :type prerequisites: List[List[int]]
        :rtype: bool
        """
        graph = self.buildGraph(numCourses, prerequisites)
        self.visted = [False] * numCourses
        self.onPath = [False] * numCourses
        for i in range(numCourses):
            self.traverse(graph, i)
        return not self.hasCiycle

    def traverse(self, graph, n):
        if self.onPath[n]:
            self.hasCiycle = True
        if self.visted[n] or self.hasCiycle:
            print(self.visted[n])
            return
        self.onPath[n] = True
        self.visted[n] = True
        for i in graph[n]:
            self.traverse(graph, i)
        self.onPath[n] = False


if __name__ == '__main__':
    s = Solution()
    numCourses = 2
    prerequisites = [[1, 0]]
    print(s.canFinish(numCourses, prerequisites))
